The universal Turing machine was devised in 1936 by Alan Turing. It was intended to mimic the pencil-and-paper operations of a mathematician. A Turing machine is a model of computation, or a way of representing and performing a given computation by means of some algorithm which is also known as the machine's “procedure.” Turing machines are mathematically and logically equivalent to many other models of computation, such as cellular automata, neural networks, and digital computers. Because no model of computation is more powerful than a Turing machine, it is considered to embody what is meant when a problem is referred to as being “computable”. In other words, anything for which an algorithm can be written, can be computed by a Turing machine. Turing machines have facilitated the proof of many important ideas and theorems regarding the nature and limits of computation, such as the undecidability of the halting problem and the existence of uncomputable functions.
While a Turing machine may be constructed to implement any specific algorithm imaginable, it is impractical to build a physical machine to solve each new problem. Fortunately, Turing machines can be constructed that take as an input a description and data tape from another Turing machine, and simulate that Turing machine on its own tape. Such a Turing machine is known as a Universal Turing Machine (UTM). Personal computers are good approximations of Universal Turing Machines, in that the programs that they run are descriptions of specific algorithms and hence, specific Turing machines. Personal computers fall short of UTMs, however, because their memory cannot be expanded every time more storage is needed. There is therefore a need in the art for Turing machines that overcome the shortcomings of, e.g., personal computers, and more closely approximate a UTM.